#include <stdio.h>
void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
/*
    ��������������dddͨ��unsorted_array���أ�
    �������������У�num_elementsΪ�������Ԫ�ظ�����
    �ɸ�����Ҫ�����������������
*/

/*�����������Ԫ�صı�Ŵ�0��ʼ��num_elements-1��
Ҫ��
1.	ʵ������������insertion_sort������
2.	�ڰѴ�1��num_elements-1λ���ϵ�ÿ��Ԫ�ط��õ�����λ����֮�󣬽���ʱunsorted_array���ȫ��Ԫ�ص�ֵ��ӡ����׼�����Ԫ��ֵ֮�����Ӣ�ĵĿո�ָ���ÿ����� ֮���С����������unsorted_array���������ΰ���4��Ԫ��4, 3, 2, 1����ô���������Ӧ�����£�
3 4 2 1
2 3 4 1
1 2 3 4

*/
void insertion_sort(int unsorted_array[], int num_elements){
    for (int j = 1; j < num_elements; j++) {
        int key = unsorted_array[j];
        int i = j - 1;
        while (i >= 0 && key < unsorted_array[i]) {
            unsorted_array[i + 1] = unsorted_array[i];
            i--;
        }
        unsorted_array[i + 1] = key;
        print_array(unsorted_array,num_elements);
    }
}


/*�����������Ԫ�صı�Ŵ�0��ʼ��total_num_elements-1��
Ҫ��
1.	ʵ������������partition��������Զѡ��lowλ���ϵ�Ԫ����Ϊpivot֧��Ԫ�أ���partition��������pivot֧��Ԫ�ص�λ��֮ǰ����unsorted_array�������Ԫ�ص�ֵ��ӡ����׼�����Ԫ��ֵ֮�����Ӣ�ĵĿո�ָ���ÿ����� ֮���С�
2.	�ݹ�ʵ������������quick_sort��������ÿ�εݹ�ʱ�ȴ������������飬�ٴ����Ҳ�������飻quick_sort�������partition������ȡpivot֧��Ԫ�ص�λ�á�
3.	���統�����unsorted_array�����Ԫ������Ϊ 3, 1, 2, 5, 4ʱ�����Ӧ��Ϊ��
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5

*/
int partition(int L[], int low,  int  high, int total_num_elements){//�ָ�
    int temp = L[low];
    int pivot = L[low];
    while(low < high){
        while(low < high&&L[high] >= pivot){
            --high;
        }
        L[low] = L[high];
        while(low < high && L[low] <= pivot){
            ++low;
        }
        L[high]=L[low];
    }
    L[low] = temp;
    print_array(L,total_num_elements);
    return low;
}
void QSort(int L[], int low,  int  high, int total_num_elements){
    if(low < high){
        int  pivotpos = partition(L,low,high,total_num_elements);

        QSort(L,low,pivotpos-1,total_num_elements);
        QSort(L,pivotpos+1,high,total_num_elements);

    }
}

void quick_sort(int unsorted_array[],int num_elements ){
    int low = 0,high = num_elements-1;
    QSort(unsorted_array,low,high,num_elements);
}


/*
�����������Ԫ�صı�Ŵ�0��ʼ��num_elements-1
Ҫ��
1.	ʵ������������heap_sort������
2.	��ÿ�ζ��Ѿ����õ����ѽ��е���Ȼ��ѵ�ǰ��������ֵ���õ�������ȷ��λ��֮���ٴε����γ�����֮ǰ����unsorted_array�������Ԫ�ص�ֵ��ӡ����׼�����Ԫ��ֵ֮�����Ӣ�ĵĿո�ָ���ÿ�����֮���С����磺
10 60 12 40 30 8 70
8 40 12 10 30 60 70
8 30 12 10 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
*/

void max_heap_down(int a[], int start, int end)
{
    int c = start;
    int l = 2 * c + 1;//start����������
    int tmp = a[c];
    for (; l <= end; c = l, l = 2 * l + 1)//��c����Ϊ�����ӣ�l����Ϊ�Һ���
    {
        if (l < end && a[l] < a[l + 1])//����Һ���С��end������,�Һ���С������
            l++;       //��l��Ϊ��������
        if (tmp >= a[l])//���c�ĺ����нϴ��Ԫ�ش��ڸ��׽ڵ�
            break;   //������ѭ��
        else           //����
        {
            a[c] = a[l];//�����׽ڵ�ͱ��Լ���ĺ��ӽ�㽻��
            a[l] = tmp;
        }
    }
}
void heap_sort(int unsorted_array[], int num_elements){
    int i;
    int swap;
    for (i = num_elements / 2 - 1; i >= 0; i--)
        max_heap_down(unsorted_array, i, num_elements - 1);
    for (i = num_elements - 1; i > 0; i--)//����n-1��ѭ������Ϊ��n-1���ڵ㶼��˳���ź��Ժ����һ��һ������Сֵ
    {   swap=unsorted_array[i];
        unsorted_array[i]=unsorted_array[0];
        unsorted_array[0]=swap;
        print_array(unsorted_array,num_elements);
        max_heap_down(unsorted_array, 0, i - 1);
    }
}
void main(){
    int test[10]={4,3,2,1};
    insertion_sort( test, 4);
    printf("\n");
    int test1[10]={3,1,2,5,4};
    QSort(test1,0,4,5);
    printf("\n");
    int test2[10]={10,60,12,40,30,8,70};
    heap_sort(test2,7);
}